"""
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。



示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
"""
import time


class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        start = time.time()
        # 我打算用嵌套循环来做，第一遍从第一个int开始挨个想加，第n遍从第n个想加
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        end = time.time()
        print(f"运行时间：{end - start}")
        return []

    # 优化的哈希表解法
    def twoSum_hashtable(self, nums, target):
        start = time.perf_counter()
        num_dict = {}
        # enumerate：它提供了对序列（如列表、元组等）进行迭代的高效方式，获得索引和值。返回的是一个枚举对象
        # 把索引和值赋给 i和 num
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_dict:
                end = time.perf_counter()
                print(f"运行时间：{end - start}")
                return [num_dict[complement], i]
            num_dict[num] = i
        return []  # 理论上不会执行


soultion = Solution()

test_cases = [
    # 标准用例（题目示例）
    ([2, 7, 11, 15], 9, [0, 1]),
    ([3, 2, 4], 6, [1, 2]),
    ([3, 3], 6, [0, 1]),

    # 负数用例
    ([-1, -2, -3], -3, [0, 1]),
    ([5, -3, 2, 0], -1, [1, 3]),

    # 零值用例
    ([0, 4, 0], 0, [0, 2]),
    ([10, 0, -10], 0, [0, 2]),

    # 重复元素（非目标值）
    ([1, 1, 2, 3], 4, [1, 3]),

    # 最大/最小值边界（10^9）
    ([10 ** 9, 1, -1], 0, [1, 2]),
    ([10 ** 9, 1, 10 ** 9], 2 * 10 ** 9, [0, 2]),

    # 大数组验证（10000个元素，耗时测试）
    (list(range(1, 10001)) + [1], 10000, [9998, 10000])  # 第9999元素(10000) + 最后元素(1) = 10001 (不符合)
    # 修正为： (list(range(1, 10001)) + [9999], 19998, [9997, 10000])  # 9999 + 9999 = 19998
]
for nums, target, expected in test_cases:
    print(f"测试用例: nums={nums[:3]}{'...' if len(nums) > 3 else ''}, target={target}")

    # 您的双重循环方法
    res_bf = soultion.twoSum_hashtable(nums, target)
    bf_correct = sorted(res_bf) == sorted(expected)  # 顺序无关

    # # 哈希表方法
    # res_ht = soultion.twoSum_hashtable(nums, target)
    # ht_correct = sorted(res_ht) == sorted(expected)

    # 输出结果
    print(f"  双重循环: 结果={res_bf}, 正确={bf_correct}")
    # print(f"  哈希表法: 结果={res_ht}, 正确={ht_correct}")
    print()
